package com.linyaonan.leetcode.medium._74;

/**
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 *
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 *  
 *
 * 示例 1：
 *
 *
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 * 输出：true
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/search-a-2d-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {

        /**
         * 横向逐层来看其实还是一个升序队列，直接二分法就可以解决，唯一特殊的地方在于通过mid映射回原有二维数组的索引
         */
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int xL = matrix.length;
        int yL = matrix[0].length;

        int start = 0;
        int end = xL * yL - 1;

        while (start <= end) {
            int mid = start + ((end - start) >> 1);
            int x = mid / yL;
            int y = mid % (yL);
            int p = matrix[x][y];
            if (p == target) {
                return true;
            } else {
                if (p < target) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return false;
    }

    /**
     * 首先使用按照每一行的第一个确定所处行
     * 再行中进行查找
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix2(int[][] matrix, int target) {
        // 1. 边界
        if (matrix[0][0] > target) {
            return false;
        }
        int mMax = matrix.length - 1;
        int nMax = matrix[0].length - 1;
        if (matrix[mMax][nMax] < target) {
            return false;
        }

        int tt = -1;
        {
            int l = 0;
            int r = mMax;
            while (l <= r) {
                int m = (l + r) >>> 1;
                int temp = matrix[m][0];
                int tempMax = matrix[m][nMax];
                if (temp == target || tempMax == target) {
                    return true;
                } else if (temp > target) {
                    r = m - 1;
                } else if (tempMax < target) {
                    l = m + 1;
                } else {
                    tt = m;
                    break;
                }
            }
        }
        // 没找到满足该数值的行数据
        if (tt == -1) {
            return false;
        }
        {
            int l = 0;
            int r = nMax;
            while (l <= r) {
                int m = (l + r) >>> 1;
                int temp = matrix[tt][m];
                if (temp == target) {
                    return true;
                } else if (temp > target) {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
        }

        return false;

    }
}